#include <iostream>
#include <unordered_map>
#include <queue>
using namespace std;

// 66.38 %
class Solution
{
  public:
	vector<int> topKFrequent(vector<int> &nums, int k)
	{
		unordered_map<int, int> freq;
		for (int i = 0; i < nums.size(); i++)
		{
			freq[nums[i]]++;
		}
		priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
		for (unordered_map<int, int>::iterator iter = freq.begin(); iter != freq.end(); iter++)
		{
			if (pq.size() == k)
			{
				if (iter->second > pq.top().first)
				{
					pq.pop();
					pq.push(make_pair(iter->second, iter->first));
				}
			}
			else
			{
				pq.push(make_pair(iter->second, iter->first));
			}
		}

		vector<int> res;
		while (!pq.empty())
		{
			res.push_back(pq.top().second);
			pq.pop();
		}
		return res;
	}
};

int main()
{
	int arr[] = {1, 1, 1, 2, 2, 3};
	int len = sizeof(arr) / sizeof(arr[0]);
	int k = 2;
	vector<int> myVector(arr, arr + len);
	myVector = Solution().topKFrequent(myVector, k);
	for (int i = 0; i < k; i++)
	{
		cout << myVector[i] << " ";
	}
	return 0;
}
